﻿#include<iostream>
using namespace std;
#include<vector>
#include<list>
#include<stack>
#include<queue>

//int main()
//
//{
//
//	int array[] = { 1, 2, 3, 4, 0, 5, 6, 7, 8, 9 };
//
//	int n = sizeof(array) / sizeof(int);
//
//	list<int> mylist(array, array + n);
//
//	auto it = mylist.begin();
//
//	while (it != mylist.end())
//
//	{
//
//		if (*it != 0)
//
//			cout << *it << " ";
//
//		else
//
//			it = mylist.erase(it);
//
//		++it;
//
//	}
//
//	return 0;
//
//}

//int main()
//
//{
//
//    queue<char> Q;
//
//    char x, y;
//
//    x = 'n'; y = 'g';
//
//    Q.push(x); Q.push('i'); Q.push(y);
//
//    Q.pop(); Q.push('r'); Q.push('t'); Q.push(x);
//
//    Q.pop(); Q.push('s');
//
//    while (!Q.empty())
//
//    {
//
//        x = Q.front();
//
//        Q.pop();
//
//        cout << x;
//
//    };
//
//    cout << y;
//    return 0;
//}

//设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
//
//实现 MinStack 类 :
//
//MinStack() 初始化堆栈对象。
//void push(int val) 将元素val推入堆栈。
//void pop() 删除堆栈顶部的元素。
//int top() 获取堆栈顶部的元素。
//int getMin() 获取堆栈中的最小元素。

//class MinStack 
//{
//public:
//    MinStack() 
//    {
//        
//    }
//
//    void push(int val) 
//    {
//        if (mindata.empty()||val <= mindata.top())
//        {
//            mindata.push(val);
//        }
//        data.push(val);
//    }
//
//    void pop() 
//    {
//        if (data.top() == mindata.top())
//        {
//            mindata.pop();
//        }
//        data.top();
//    }
//
//    int top() 
//    {
//        return data.top();
//    }
//
//    int getMin() 
//    {
//        return mindata.top();
//    }
//private:
//    stack<int>data;
//    stack<int>mindata;
//
//};

//
//输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
//例如序列1, 2, 3, 4, 5是某栈的压入顺序，序列4, 5, 3, 2, 1是该压栈序列对应的一个弹出序列，但4, 3, 5, 1, 2就不可能是该压栈序列的弹出序列。
//1. 0 <= pushV.length == popV.length <= 1000
//2. - 1000 <= pushV[i] <= 1000
//3. pushV 的所有数字均不相同

class Solution 
{
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
    {
        stack<int>a;
        int i = 0;

        for (auto it : pushV)
        {
            a.push(it);
            while (!a.empty() && a.top() == popV[i])
            {
                ++i;
                a.pop();
            }
        }
        if (a.empty())
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};